package LiKou;

public class QuickSort2 {
    public static void main(String[] args) {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        Quick3(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
    public static void Quick2(int[] arr,int left,int right){
        if(left>right){
            return;
        }
        int key=arr[left];
        int pre=left;
        int cur=left+1;
        while(cur<=right){
            if(arr[cur]<=key && ++pre!=cur){
                int temp=arr[cur];
                arr[cur]=arr[pre];
                arr[pre]=temp;
            }
            cur++;
        }
        int temp=arr[left];
        arr[left]=arr[pre];
        arr[pre]=temp;
        Quick2(arr,pre+1,right);
        Quick2(arr,left,pre-1);
    }
    public static void Quick3(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int key=arr[left];
        int i=left;
        int j=right;
        while(i<j){
            while(j>i && arr[j]>=key){
                j--;
            }
            if(j>i){
                arr[i]=arr[j];
            }
            while(i<j && arr[i]<=key){
                i++;
            }
            if(j>i){
                arr[j]=arr[i];
            }
        }
        arr[i]=key;
        Quick3(arr,left,i-1);
        Quick3(arr,i+1,right);
    }
}
